#include<iostream>
using namespace std;

int nextarr[100];
int nextvalarr[100];
void getnext(string t) {//求next数组
	int j = 0, k = -1;
	nextarr[0] = -1;
	while (j < t.length()) {
		if (k == -1 || t[j] == t[k]) {
			j++, k++;
			nextarr[j] = k;
		}
		else {
			k = nextarr[k];
		}
	}
	for (int i = 0; i < t.length(); i++) {
		cout << nextarr[i] << ' ';
	}
}

void getnextval(string t) {//求nextval数组
	int j = 0, k = -1;
	nextvalarr[0] = -1; 
	while (j < t.length()) {
		if (k == -1 || t[j] == t[k]) {
			j++, k++;
			if (t[j] == t[k]) {
				nextvalarr[j] = nextvalarr[k];
			}
			else {
				nextvalarr[j] = k;
			}
		}
		else {
			k = nextvalarr[k];
		}
	}for (int i = 0; i < t.length(); i++) {
		cout << nextvalarr[i] << ' ';
	}
}

int KMP(string s,string t) {//KMP匹配
	int i = 0, j = 0;
	int answer = 0;
	while (i < s.length()) {
		if (j == -1 || s[i] == t[j]) {
			i++, j++;
		}
		else {
			j = nextarr[j];
		}
		if (j == t.length()) {
			answer = i - t.length();
			return answer;
		}
	}
	return -1;
}

int newKMP(string s, string t) {//KMP改进算法
	int i = 0, j = 0;
	while (i < s.length() && j < t.length()) {
		if (j == -1 || s[i] == t[j]) {
			i++, j++;
		}
		else {
			j = nextvalarr[j];
		}
	}
	if (j = t.length()) { return i - j; }
	else { return -1; }
}

int simplefind(string s, string x) {//简单匹配算法
	int i = 0, j = 0, index = 0;
	while (i < s.length() && j < x.length()) {
		if (s[i] == x[j]) {
			i++; j++;
		}
		else {
			j = 0;
			index++;
			i = index;
		}
	}
	if (j == x.length()) {
		return index;
	}
	return 0;
}

int main()
{
	string s = "abcabcdabcdeabcdefabcdefg";
	string t = "abcdeabcdefab";
	cout << "简单匹配算法求出位置：" << simplefind(s, t) << endl;
	cout << "获取next数组：";
	getnext(t);
	cout << endl;
	cout << "获取nextval数组：";
	getnextval(t);
	cout << endl;
	cout << "使用KMP算法求出位置：" << KMP(s, t) << endl;
	cout << "使用改进KMP算法求出位置：" << newKMP(s, t) << endl;
}


